/*
 * @lc app=leetcode.cn id=142 lang=typescript
 *
 * [142] 环形链表 II
 * Floyd 判圈法
 * 给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。
 * 每次 fast 前进两步，slow 前进一步。
 * 如果 fast 可以走到尽头，那么说明没有环路;
 * 如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。
 * 当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。
 * 当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head, fast = head

    do {
        if (fast === null || fast.next === null) return null
        fast = fast.next.next
        slow = slow.next
    } while (slow !== fast)

    fast = head
    while (fast !== slow) {
        fast = fast.next
        slow = slow.next
    }
    return fast
};
// @lc code=end

